package top.humbleyuan.divide_conquer;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

import java.util.Arrays;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-07
 * @Time: 13:54
 * @Description: 合并k个有序链表
 */
public class LeetCode_23 {
    /**
     * 分治法
     * 将链表两两分组，合并
     * 最终合并成一个
     */
    public static void main(String[] args) {
        // 构造
        LinkNode l1 = new LinkNode(2);
        LinkNode.formLink(l1, new int[]{3, 4});

        LinkNode l2 = new LinkNode(5);
        LinkNode.formLink(l2, new int[]{6, 9});

        LinkNode l3 = new LinkNode(1);
        LinkNode.formLink(l3, new int[]{2, 10});

        LinkNode[] lists = new LinkNode[] {l1, l2, l3};

        // 分治
        LinkNode res = m1(lists);
        LinkNode.headToString(res);
    }

    public static LinkNode m1(LinkNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        if(lists.length == 1) {
            return lists[0];
        }
        if(lists.length == 2) {
            return mergeTwo(lists);
        }
        int mid = lists.length / 2;

        LinkNode[] left = Arrays.copyOfRange(lists, 0, mid);
        LinkNode[] right = Arrays.copyOfRange(lists, mid, lists.length);
        LinkNode leftNode = m1(left);
        LinkNode rightNode = m1(right);

        return mergeTwo(new LinkNode[]{leftNode, rightNode});
    }

    public static LinkNode mergeTwo(LinkNode[] lists) {
        LinkNode res = new LinkNode(0);
        LinkNode temp = new LinkNode(0);
        res.next = temp;
        while(lists[0] != null || lists[1] != null) {
            int num1 = lists[0] == null ? Integer.MAX_VALUE : lists[0].val;
            int num2 = lists[1] == null ? Integer.MAX_VALUE : lists[1].val;

            if(lists[0] == null || num1 > num2) {
                temp.next = lists[1];
                temp = temp.next;
                lists[1] = lists[1].next;
                continue;
            }

            if(lists[1] == null || num1 <= num2) {
                temp.next = lists[0];
                temp = temp.next;
                lists[0] = lists[0].next;
            }
        }

        return res.next.next;
    }
}
